package linkedlist;

import datastructure.ListNode;
/**
 * https://leetcode-cn.com/problems/add-two-numbers/
 */
public class M2_AddTwoNumbers {
    /**
     * 时间复杂度 O(n) 空间复杂度 O(m+n)
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 无效节点
        if (l1 == null && l2 == null) {
            return null;
        }
        // 创建存放结果的链表及其头指针
        ListNode head = new ListNode(0);
        ListNode dummyNode = head;
        // 进位符号
        int addOne = 0;
        // l1和l2节点都不为空且符号的值大于0
        while (l1 != null || l2 != null || addOne > 0) {
            // 取节点的val值并求和
            int l1_Val = l1 != null ? l1.val : 0;
            int l2_Val = l2 != null ? l2.val : 0;
            int sum = l1_Val + l2_Val + addOne;
            // 创建dummy节点的下一个节点，新节点的值是sum取模的值(不含进位符)
            dummyNode.next = new ListNode(sum%10);
            // 更新dummy节点的位置(dummy节点后移)
            dummyNode = dummyNode.next;
            // 更新进位符的值
            addOne = sum / 10;
            // 后移指针指向待计算的节点
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }
        return head.next;
    }
}
